class Solution
{
public:
    int minimumEffortPath(vector<vector<int>> &heights)
    {
        int m = heights.size();
        int n = heights[0].size();
        auto checkAns = [&](int x)
        {
            queue<pair<int, int>> q;
            vector<vector<int>> visited(m, vector<int>(n, 0));
            q.push({0, 0});
            visited[0][0] = 1;
            while (!q.empty())
            {
                auto [i, j] = q.front();
                q.pop();
                if (i == m - 1 && j == n - 1)
                {
                    return true;
                }
                if (i > 0 && !visited[i - 1][j] && abs(heights[i][j] - heights[i - 1][j]) <= x)
                {
                    q.push({i - 1, j});
                    visited[i - 1][j] = 1;
                }
                if (j > 0 && !visited[i][j - 1] && abs(heights[i][j] - heights[i][j - 1]) <= x)
                {
                    q.push({i, j - 1});
                    visited[i][j - 1] = 1;
                }
                if (i < m - 1 && !visited[i + 1][j] && abs(heights[i][j] - heights[i + 1][j]) <= x)
                {
                    q.push({i + 1, j});
                    visited[i + 1][j] = 1;
                }
                if (j < n - 1 && !visited[i][j + 1] && abs(heights[i][j] - heights[i][j + 1]) <= x)
                {
                    q.push({i, j + 1});
                    visited[i][j + 1] = 1;
                }
            }
            return false;
        };

        int l = 0, r = 1e6 + 5;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (checkAns(mid))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;
    }
};